package sortAlgorithm;

/**
 * 堆排序
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] nums = new int[]{3,6,8,5,9};
        // 构造堆
        for (int i = nums.length/2; i >= 0 ; i--) {
            heapAdjust(nums, i, nums.length);
        }
        // 将堆顶元素和堆尾元素进行交换 并构造新的大顶堆
        for (int j = nums.length-1; j > 1 ;j--) {
            int t = nums[0];
            nums[0] = nums[j];
            nums[j] = t;
            heapAdjust(nums, 0, j-1);
        }
        System.out.println(nums);
    }

    /**
     * 对数组中下标为 0~len-1 的数进行堆的构造
     * */
    private static void heapAdjust(int[] arr, int s, int len){

        // 对于下标为s的根节点 其左孩子结点为 2s+1
        for (int i = 2*s+1; i < len; i = 2*i+1){
            if(arr[i] < arr[i+1]){
                ++i;
            }
            // 这里表示 左右孩子结点都比根节点小 那么就不走后续的交换流程了
            if(arr[s] > arr[i]){
                return ;
            }
            // 根节点跟最大的孩子结点交换
            int temp = arr[s];
            arr[s] = arr[i];
            s=i;
            arr[i] = temp;
        }

    }
}
